\section{动态顺序统计}

\begin{enumerate}[label=\textbf{\thesection{}-\arabic*}]
  \item
  \item
  \item \textbf{写出OS-SELECT的非递归形式。}

\begin{alltt}
OS-SELECT(\(x\), \(i\))
    \(r\gets{}size[left[x]]+1\)
    while \(i\ne{}r\)
        do if \(i<r\)
               then \(x\gets{}left[x]\)
               else \(x\gets{}right[x]\)
           \(r\gets{}size[left[x]]+1\)
    return \(x\)
\end{alltt}

  \item \textbf{写出一个递归过程OS-KEY-RANK($T$, $k$)，使之以一棵顺序统计树$T$和某个关键字$k$为输入，返回在由$T$表示的动态集合中$k$的秩。假设$T$的所有关键字都是不同的。}

\begin{alltt}
OS-KEY-RANK(\(T\), \(k\))
    \(r\gets{}size[left[x]]+1\)
    if \(k=key[T]\)
        then return \(r\)
    else if \(k<key[T]\)
        then return OS-KEY-RANK(\(left[T]\), \(k\))
    else return \(r+\text{OS-KEY-RANK(}right[T]\text{, }k\text{)}\)
\end{alltt}

  \item \textbf{给定含$n$个元素的顺序统计树中的一个元素$x$和一个自然数$i$，如何在$O(\text{lg}n)$时间内，确定$x$在该树的线性序中第$i$个后继？}

\begin{alltt}
OS-SUCCESSOR(\(T\), \(x\), \(i\))
    \(r\gets{}\text{OS-RANK(}T\text{, }x\text{)}+i\)
    return OS-SELECT(\(root[T]\), \(r\))
\end{alltt}

  \item \textbf{在OS-SELECT或OS-RANK中，每次引用结点的$size$域都仅是为了计算在以结点为根的子树中该结点的秩。假设我们将每个结点的秩（对于以该结点为根的子树而言）存于该结点自身之中。说明在插入和删除时如何来维护这个信息（注意这两种操作可能引起旋转）。}

        对于插入操作，第一阶段新结点若为经过结点左子树中的结点，则该经过结点的$rank$值加1。第二阶段，针对左旋情况，$rank[x]$不变，$rank[y]\gets{}rank[x]+1$，右旋情况是对称的。

        对于删除操作，第一阶段同插入操作，只是$rank$值需要变为减1。第二阶段与插入操作完全相同。
\end{enumerate}